package offer.zixing.chapter05;

import java.util.*;

/**
 * 变位词组
 *
 * 给定一组单词，请将它们按照变位词分组。例如输入一组单词["eat", "tea", "tan", "ate", "nat", "bat"]，
 * 则可以分成三组，分别是["eat", "tea", "ate"]、["tan", "nat"]和["bat"]。假设单词中只包含小写的英文字母。
 */
public class Test033 {

    static String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};

    public static void main(String[] args) {
        System.out.println(groupAnagrams1(strs));
        System.out.println(groupAnagrams2(strs));
    }

    public static List<List<String>> groupAnagrams1(String[] strs) {
        int hash[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
        Map<Long, List<String>> groups = new HashMap<>();
        for (String str : strs) {
            long wordHash = 1;
            for (int i = 0; i < str.length(); i++) {
                wordHash *= hash[str.charAt(i) - 'a'];
            }
            groups.putIfAbsent(wordHash, new LinkedList<String>());
            groups.get(wordHash).add(str);
        }
        return new LinkedList<>(groups.values());
    }

    public static List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sorted = new String(charArray);
            // putIfAbsent在放入数据时，如果存在重复的key，那么putIfAbsent不会放入值。
            groups.putIfAbsent(sorted, new LinkedList<String>());
            groups.get(sorted).add(str);
        }
        return new LinkedList<>(groups.values());
    }
}
